package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/3 9:06
 * @description :https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
 */
public class 最短无序连续子数组 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findUnsortedSubarray(new int[]{2,2,4}));
    }

    /*
    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int[] sortNum = new int[nums.length];
            System.arraycopy(nums, 0, sortNum, 0, nums.length);
            quick_sort(nums, 0, nums.length - 1);
            int left = 0;
            while (left < nums.length && nums[left] == sortNum[left]) left++;
            if (left == nums.length) return 0;
            int right = nums.length - 1;
            while (nums[right] == sortNum[right]) {
                right--;
            }
            return right - left + 1;
        }

        private void quick_sort(int[] nums, int left, int right) {
            if (left >= right) return;
            int l = left;
            int r = right;
            int pivot = nums[l];
            while (l < r) {
                while (l < r && nums[r] >= pivot) {
                    r--;
                }
                nums[l] = nums[r];
                while (l < r && nums[l] <= pivot) {
                    l++;
                }
                nums[r] = nums[l];
                nums[l] = pivot;
            }
            quick_sort(nums, left, r - 1);
            quick_sort(nums, r + 1, right);
        }
    }
     */

    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            if (isSorted(nums)) {
                return 0;
            }
            int[] numsSorted = new int[nums.length];
            System.arraycopy(nums, 0, numsSorted, 0, nums.length);
            Arrays.sort(numsSorted);
            int left = 0;
            while (nums[left] == numsSorted[left]) {
                left++;
            }
            int right = nums.length - 1;
            while (nums[right] == numsSorted[right]) {
                right--;
            }
            return right - left + 1;
        }

        public boolean isSorted(int[] nums) {
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < nums[i - 1]) {
                    return false;
                }
            }
            return true;
        }
    }
}
